A computer or other type of data processing system can create, maintain, and process data of various data types and can use various types of data structures, such as, for example, key-value maps. A key-value map (or associative array) is a data type or structure that is composed of a collection of key-value pairs. Typically, each key in a key-value map appears at most once in the key-value map. That is, each key is associated with, at most, one slot of the key-value map, where the key-value map comprises a plurality of slots or entries. Further, each slot of a key-value map is associated with a single key. The association between a key and a value is known as a binding. In some cases, binding may also refer to the process of creating a new key-value association.
A number of operations can be defined for a key-value map. These operations can include add operations, remove operations, and lookup operations. An add or insert operation adds a new key-value pair to the map by binding a key to given value. A remove or delete operation removes a key-value pair from the map, unbinding a given key from its value. Given a key, a lookup or get operation locates and returns a value in a key-value map that is bound or associated with the given key if the key is valid.
Key-value maps are sometimes used in conjunction with data buffers. For example, a data buffer can be implemented as a circular buffer such that one or more locations in the data buffer each include a key that references a value in the key-value map. The values stored in the key-value map can be referenced from the data buffer multiple times using the associated keys.
It may be desirable to reuse slots in a key-value map. That is, it may be desirable to immediately assign a new key-value pair to a slot of a key-value map after a bound key-value pair is deleted from that slot. However, reusing slots of a key-value map may not be efficient when the key-value map is used in conjunction with a data buffer, because the slot cannot be reused until the key for that slot is no longer referenced in the corresponding data buffer. For example, when a key is deleted from the key-value map, there may still be multiple references to the key in the data buffer. Accordingly, reusing the slot of the key-value map prior to all of the references being deleted can result in the key-value map incorrectly providing a deleted value in response to a lookup operation. Further, while deleting a key-value pair from a slot of a key-value map is a relatively easy and efficient process, deleting the one or more entries in the buffer that reference the key may not be practical due to performance issues (e.g., assuming each of the now invalid key references must be found and deleted, potentially resulting in an unbounded number of operations). Additionally, if the data buffer is implemented in a flash memory, finding and deleting each of the entries corresponding to the now invalid key can result in excessive flash wear.
One example of a data processing system that may use key-value maps is a network storage controller. A network storage controller is a physical processing device that is used to store and retrieve data on behalf of one or more hosts. A network storage controller can be configured (e.g., by hardware, software, firmware, or any combination thereof) to operate as a storage server that serves one or more clients on a network, to store and manage data in a set of mass storage devices, such as magnetic or optical storage-based disks, tapes, or flash memory. Storage of data in the set of mass storage devices can be implemented as one or more storage volumes defining an overall logical arrangement of disk space.
Some storage servers are designed to service file-level requests from hosts, as is commonly the case with file servers used in a network attached storage (NAS) environment. Other storage servers are designed to service block-level requests from hosts, as with storage servers used in a storage area network (SAN) environment. Still other storage servers are capable of servicing both file-level requests and block-level requests, as is the case with certain storage servers made by NetApp®, Inc. of Sunnyvale, Calif., employing the Data ONTAP® storage operating system.
Typically, it is beneficial for a storage administrator to be able to add and delete storage containers (e.g., volumes, files, directories or logical units) that have identifiers that are referenced in a key-value map. However, the number of storage containers that can use the data buffer are limited to the number of slots available in a key-value map. Thus, the current methods and systems for reusing slots of a key-value map are not efficient because an administrator must wait for the key to no longer be referenced in the data buffer before reusing the slot of the key-value map, to ensure that data related to a deleted (or invalid) key is not referenced.